package com.dhnsoft.代码随想录.栈与队列;

import java.util.*;

/**
 * ClassName: d06_239_滑动窗口最大值
 * Package: com.dhnsoft.代码随想录.栈与队列
 * Description:
 *
 * @Author dhn
 * @Create 2024/3/28 19:50
 * @Version 1.0
 */
public class d06_239_滑动窗口最大值 {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(k>nums.length){
            return null;
        }
        int max=Integer.MIN_VALUE;
        Queue<Integer> queue = new ArrayDeque();
        int[] arr = new int[nums.length-k+1];
        int j = 0;
        for (int i=0;i<k;i++){
            max = Math.max(nums[i],max);
            queue.offer(nums[i]);
        }
        arr[j++]=max;
        for (int i=k;i<nums.length;i++){
            queue.poll();
            queue.offer(nums[i]);
            max = Integer.MIN_VALUE;
            for (Integer integer : queue) {
                max = Math.max(integer,max);
            }
            arr[j++] = max;
        }
        return arr;
    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        if(k>nums.length){
            return null;
        }
        Deque<Integer> queue = new LinkedList<>();
        int[] arr = new int[nums.length-k+1];
        int j = 0;
        for (int i=0;i<nums.length;i++){
            //队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while (!queue.isEmpty()&&queue.peek()<i-k+1){
                queue.poll();
            }
            //限制只让大于当前队列头元素进来，并且将队列头元素pop出去,传入到队列中的是数组的下标
            while (!queue.isEmpty()&&nums[i]>nums[queue.peekLast()]){
                queue.pollLast();
            }
            queue.offer(i);
            //因为是单调队列，所以每次的队头都是最大值，把最大值加入到数组即可，由于取数是从k-1开始后开始取的
            if(i>=k-1){
                arr[j++]=nums[queue.peek()];
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1,-1}, 1)));
    }
}
